#pragma once

#include <vector>

namespace solution_096
{

class Solution {
public:
    int numTrees(int n)
    {
        std::vector<int> g(n + 1, 0);
        g.at(0) = 1;
        g.at(1) = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j)
                g.at(i) += g.at(j - 1) * g.at(i - j);
        }
        return g.back();
    }
};

}  /* namespace solution_096 */
